perm filename READC[B2,JMC] blob
sn#772688 filedate 1984-10-18 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00004 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \section{Numerical computation.}
C00019 00003 \section{Lambda expressions and functions with functions as arguments.}
C00034 00004 \section{The {\it read eval print\/} loop.}
C00062 ENDMK
C⊗;
\section{Numerical computation.}
\sectlab{numbers}
Numerical calculation and symbolic calculation must often
be combined, so \lisp\ provides for numerical computation also.
(If we wanted to do everything with lists, we could represent numbers
as lists of digits, but then it
would be difficult to take proper advantage of machine instructions
that work with numbers directly).
Since we need to include numbers as parts
of symbolic expressions, \lisp\ has both integer and floating point
numbers which are regarded as atoms when they are
included in S-expressions.
Thus we have the lists:
$$\vbox{%
\ialign{ #\hfil\cr
|(1 3 5)| \cr
|(3.5 6.1 -7.2E9)|\cr
|(+ X 1.3)| \cr
}}$$
The first
is a list of integers, the second a list of floating point numbers,
and the third a symbolic list containing both numerical and
non-numerical atoms. Integers are written without decimal points
which are used to signal floating point numbers. As in FORTRAN,
the letter E is used to signal the exponent of a floating point
number which is a signed integer. The sizes of numbers admitted
depends on the implementation. When a dotted pair, say |(1 . 2)|
is wanted, the spaces around the dot distinguish it from the
list |(1.2)| whose sole element is the floating point number 1.2.
In external language we will use ordinary mathematical
notation for numerical functions. As an example of a function
combining numeric and symbolic calculation we have the function
giving the length of a list defined by
\beginlisp
(DEFUN LENGTH (U)
(COND ((NULL U) 0) (T (ADD1 (LENGTH (CDR U)))) ))
(bb tex '(length))
\endlisp
\beginfundef
\funlab{length}
\hskip0\unit length u ← \qif \qn u \qthen 0 \qelse
\qaddone length \qd u\cr
\endfundef
The internal notation for numerical functions is shown in
the following examples:
$$\vbox{%
\ialign{#\hfil\cr
|(+ X Y ... Z)| for $x+y+...+z$,\cr
|(* X ... Z)| for $xy...z$, \cr
|(- X)| for $-x$,\cr
|(- X Y)| for $x-y$, \cr
|(/ X Y)| for $x\div y$,\cr
|(EXPT X Y)| for $x↑y$.\cr
}}$$
Besides functions of numbers we need predicates on numbers
and the usual \qequal, \qlt, \qgt, \qlte, and \qgte\ are used with the internal
names |EQUAL|, |<|, |>|, |<=|, and |>=|, respectively.
Not all are implemented in all \lisp\ systems, but of course the
remaining ones can be defined. There is an additional predicate, /numberp/,
that is true of an object if and only if it is a number.
Since numbers that form part of list structures must be
represented by pointers anyway, there is room for a flag distinguishing
floating point numbers and integers. Therefore, the arithmetic
operations are programmed to treat types dynamically, i.e. a variable
may take an integer value at one step of computation and a real value
at another. The subroutines realizing the arithmetic functions make
the appropriate tests and create results of appropriate types.
It is worth remarking that including type flags in numbers
benefits many programming languages besides \lisp\ and doesn't
cost much in either storage or hardware. The \lisp\ machines
include such flags.
Dynamic typing of variables is slow compared to direct use of
the machine's arithmetic instructions, so that \lisp\ can be efficiently
used interpretively only when
the numerical calculations are small or at least small compared
to the symbolic calculations in a problem.
The \clisp\ compiler is able to generate efficient
arithmetic code. In particular, variables can be declared to be of a fixed
numerical type and the correct machine instructions are then generated
so that runtime testing is not necessary. Also, it uses separate stacks
to store numerical results so that unnecessary conversion from the
\lisp\ representation of a number to the machine representation can be
avoided. This saves both time and space as each conversion from a
machine number to a \lisp\ number requires a /cons/ operation.
\lisp\ can also deal with integers too large to be represented
as a single machine word. Such numbers are called ``bignums'' and
are represented in \lisp\ by a pointer to a list structure which contains the
sign, a flag saying that this a ``bignum'', and a list of the numbers
corresponding to a base B representation of the number for some
suitable B (depending on the machine and implementation).
As another example of a combined numeric and symbolic
computation, we give an evaluator for expressions with sums and
products. We shall also take this as an opportunity to demonstrate the
the use of abstract syntax, a subject that we shall devote a whole chapter
to later in the book.The expressions that we shall be evaluating
are built up from symbols
denoting variables and integer constants in the following fashion
1. A symbol or a number is an expression.
2. If $e_1$, $e_2$, \dots $e_n$ are expressions then so are
|(+| $e_1$ $e_2$ \dots $e_n$|)|
and |(*| $e_1$ $e_2$ \dots $e_n$|)|.
Thus a list of expressions beginning with either the symbol |+| or the symbol
|*| is an expression. The former represents the sum of these expressions
while the later represents the product of them. Another way to describe abstractly
our domain of expressions is to use the constructor functions /mksum\// and
/mkprod\// where
\beginlisp
(DEFUN MKSUM (ELIST) (CONS '+ ELIST))
(DEFUN MKPROD (ELIST) (CONS '* ELIST))
(bb tex '(mksum mkprod))
\endlisp
\beginfundef
\funlab{mksum}
\funlab{mkprod}
\hskip0\unit mksum elist ← |+| \qcons elist\cr
\noalign{\medskip}
\hskip0\unit mkprod elist ← |*| \qcons elist\cr
\endfundef
Using this method the above definition becomes
$1'$. A symbol or a number is an expression.
$2'$. If {\it elist\/} is a list of expressions then $/mksum/[{\it elist\/}]$ and
$/mkprod/[{\it elist\/}]$ are expressions.
The reason why one would choose the later method is that it enables one to write the
program /numval\// in a style that emphasizes the algorithm rather than the
particular representation of the data chosen. It also allows one to alter the
representation at a later date without having to change the program, except for
modifying the definitions of the functions that deal explicitly with the
representation. In writing the program /numval\// we shall also need the functions
/sump/, /prodp/, /varp/, /lookup\// and /arglist/. Using the above
representation as lists these are defined as
\beginlisp
(DEFUN SUMP (e) (EQ (CAR e) '+))
(DEFUN PRODP (e) (EQ (CAR e) '*))
(DEFUN VARP (e) (AND (ATOM e) (NOT (NUMBERP e))))
(DEFUN LOOKUP (e a) (CDR (ASSOC e a)))
(DEFUN ARGLIST (e) (CDR e))
(bb tex '(sump prodp varp lookup arglist))
\endlisp
\beginfundef
\funlab{sump}\funlab{prodp}\funlab{varp}\funlab{lookup}\funlab{arglist}
\hskip0\unit sump e ← \qa e \qeq |+|\cr
\noalign{\medskip}
\hskip0\unit prodp e ← \qa e \qeq |*|\cr
\noalign{\medskip}
%
\hskip0\unit varp e ← \qat e \qand \qnot numberp e\cr
\noalign{\medskip}
%
\hskip0\unit lookup[e, a] ← \qd assoc[e, a]\cr
\noalign{\medskip}
%
\hskip0\unit arglist e ← \qd e\cr
\endfundef
In order to evaluate an expression we need a way of giving values to the
variables occuring in the expression. We will use an {\it association list\/} for
this purpose. An association list (a-list) is a list of pairs, in our
case the first
element of each pair is a variable and the second element is the value associated
with it. For example $|((X . 5) (Y . 9.3) (Z . 2.1))|$ is an a-list.
To look up the value of a variable in an a-list we use the function /assoc/,
which returns the first pair in the list such that the variable matches
the variable argument. It returns \qNIL\ if no value is found. Thus
%
$$/assoc/[|Y|,|((X . 5) (Y . 9.3) (Z . 2.1))|] = |(Y . 9.3)|.$$
and the definition of /assoc\// is given by
\beginlisp
(DEFUN ASSOC (X A)
(COND ((NULL A) NIL) ((EQ X (CAAR A)) (CAR A)) (T (ASSOC X (CDR A))) ))
(bb tex '(assoc))
\endlisp
\beginfundef
\funlab{assoc}
\hskip0\unit assoc[x, a] ← \qif \qn a \qthen
\qNIL \qelsif x \qeq \qaa a \qthen \qa a \qelse assoc[x, \qd a]\cr
\endfundef
Association lists are generally useful for associating ``values'' with ``symbols''
and they will appear in many later examples. We note here two features
which are due to the way /assoc\// is defined. Since /assoc\// returns the
pair rather than the value when the desired symbol is found or \qNIL\
if no value is found, the case of no value found can be detected.
If just the value were returned there would be no distinction between no
value and a value of \qNIL. The calling program must check to see if a value
was returned ($\qnot \qn /assoc/[x,a]$) and then extract that value
($\qd /assoc/[x,a]$).
Also, /assoc\// returns the first pair it finds, thus a symbol can be
associated with several values in the a-list, but always the first occurrence
determines the result that is returned. Thus
$$/assoc/[|X|,|((U . 1.41) (X . 5) (Y . 9.3) (X . 1.2) (Z . 2.1))|] = |(X . 5)|.$$
/assoc/ is built into most \lisp\ systems.
The interpreter, /numval/, can now be defined.
\beginlisp
(DEFUN NUMVAL (e a)
(IF
(NUMBERP e)
e
(IF
(VARP e)
(LOOKUP e a)
(IF (SUMP e)
(SUMVAL (ARGLIST e) a)
(IF (PRODP e) (PRODVAL (ARGLIST e) a) 'ERROR)))))
(bb tex '(numval))
\endlisp
\beginfundef
\funlab{numval}
\xx0 numval[e, a] ← \cr
\xx4 \qif numberp e \qthen e\cr
\xx4 \qelsif varp e \qthen lookup[e, a]\cr
\xx4 \qelsif sump e \qthen sumval[arglist e, a]\cr
\xx4 \qelsif prodp e \qthen prodval[arglist e, a]\cr
\xx4 \qelse |ERROR|\cr
\endfundef
where
\beginlisp
(DEFUN SUMVAL (e a)
(IF (NULL e) 0 (+ (NUMVAL (CAR e) a) (SUMVAL (CDR e) a))))
(DEFUN PRODVAL (e a)
(IF (NULL e) 1 (* (NUMVAL (CAR e) a) (PRODVAL (CDR e) a))))
(bb tex '(sumval prodval))
\endlisp
\beginfundef
\funlab{sumval}
\funlab{prodval}
\xx0 sumval[e, a] ← \qif \qn e \qthen 0 \qelse numval[\qa e, a] + sumval[\qd
e, a]\cr
\noalign{\medskip}
%
\xx0 prodval[e, a] ← \qif \qn e \qthen 1 \qelse numval[\qa e, a] \times
prodval[\qd e, a]]\cr
\endfundef
\exercise Rewrite $numval$ using the appropriate mapping functions.
\section{Lambda expressions and functions with functions as arguments.}
\sectlab{lambda}
It is common to use phrases like ``the function $2x+y$''. This
is not a precise notation because we cannot say $[2x+y][3,4]$ and know
whether the desired result is $2\times3+4$ or $2\times4+3$ regarding the
expression as a function of two variables. Worse yet, we might have
meant a one-variable function of $x$ wherein $y$ is regarded as a
parameter.
Church's $\lambda$-notation provides a convenient way of giving names
to functions. In the above example, we would write
$\lambda x\,y.2x+y$ to denote the function of two variables with first
argument $x$ and second argument $y$ whose value is given by the
expression $2x+y$. Thus, $[\lambda x\,y.2x+y][3,4]=10$ and
$[\lambda y\,x. 2x+y][3,4]= 11$.
Notice however that there is a big difference between $\lambda x\,y.2x+y$ and
$\lambda x\,\lambda y.2x+y$. The former is a function of two arguments while
the later is a function of one argument that returns a function of one argument.
Not all \lisp\ implementations support the later construct although \clisp\ does.
Like variables of integration
and the bound variables of quantifiers in logic, variables following
the $\lambda$ are bound or dummy and may be replaced by any others
provided the replacement is done consistently throughout the
expression and does not
make any variable bound by $\lambda$ the same as a free variable in the
expression. Thus $\lambda x\,y. 2x+y$ represents the same function as
$\lambda y\,x. 2y+x$ or $\lambda u\,v. 2u+v$, but in the function of one argument
$\lambda x.2x+y$, we cannot replace the variable $x$ by $y$, though we could
replace it by $u$.
$\lambda$-notation plays two important roles in \lisp. First, it
allows us to rewrite an expression containing two or more occurrences
of the same sub-expression in such a way that the expression occurs
only once. Thus $(2x+1)↑4 +3(2x+1)↑3$ can be written
$[\lambda w.w↑4+3w↑3][2x+1]$. This can save considerable
computation, and
corresponds to the practice in sequential programming of assigning to a
variable the value of a sub-expression that occurs more than once in
an expression and then writing the expression in terms of the
variable. It is sometimes called $\lambda$-binding.
The second use of $\lambda$-expressions is in using functions that
take functions as arguments. Suppose we want to form a new list from
an old one by applying a function $f$ to each element of the list.
This can be done using the function /mapcar/ defined by
%
\beginlisp
(DEFUN MAPCAR1(FN U)
(COND ((NULL U) NIL) (T (CONS (FN (CAR U)) (MAPCAR1 FN (CDR U)))) ))
(bb tex '(mapcar1))
% Change mapcar1 to mapcar. Something weird happens to lisp if mapcar is
% redefined this way, and TRACE stops working properly.
\endlisp
\beginfundef\funlab{mapcar}
\xx0 mapcar[fn, u] ← \qif \qn u \qthen \qNIL \qelse fn \qa u \qcons
mapcar[fn, \qd u]\cr
\endfundef
%
or in internal notation as
%
\begindefun
(DEFUN MAPCAR (F U)
(IF (NULL U) NIL (CONS (FUNCALL F (CAR U)) (MAPCAR F (CDR U)))))
\enddefun
Such a function is called a {\it functional\/} since one (or more) of its arguments
is a function. /mapcar\// maps a function and a list into a list.
Suppose the operation we want to perform is squaring, and we want to
apply it to the list |(1 2 3 4 5 6 7)|. We have
$$/mapcar/[\lambda x. x↑2, |(1 2 3 4 5 6 7)|] = |(1 4 9 16 25 36 49)|.$$
[Some implementations of \lisp\ allow mapping functions to take
an arbitrary number of lists as arguments. The number of lists is the
number of arguments expected by the functional argument and the mapping
terminates when the shortest list is exhausted. Some implementations
of \lisp\ require the arguments in reverse order - functional argument
second.]
A more general operation than /mapcar\// is /maplist\//
in which the function is applied to the successive sublists of the
list rather than to the elements. /maplist\// is defined by
\beginlisp
(DEFUN MAPLIST (F U) (COND ((NULL U) NIL) (T (CONS (F U) (MAPLIST F (CDR U)))) ))
(bb tex '(maplist))
\endlisp
\beginfundef\funlab{maplist}
\xx0 maplist[f, u] ← \qif \qn u \qthen \qNIL \qelse f u \qcons maplist[f,
\qd u]\cr
\endfundef
As an application of /maplist\// and /mapcar\//
with functional arguments, we
shall define a function for differentiating algebraic expressions
involving sums and products.
The syntax for such expressions was given in \sectref{numbers}.
Recall that |+| followed by a list of arguments denotes the sum of these
arguments, and |*| followed by a list of arguments denotes their
product. The function $/diff/[e,v]$ gives the partial derivative of
the expression $e$ with respect to the variable $v$. We have
\beginlisp
(DEFUN DIFF (E V)
(COND ((ATOM E) (IF (EQ E V) 1 0))
((SUMP E)
(MKSUM
(MAPCAR (FUNCTION (LAMBDA (X) (DIFF X V))) (CDR E))))
((PRODP E)
(MKSUM
(MAPLIST (FUNCTION
(LAMBDA (X)
(MKPROD
(MAPLIST (FUNCTION
(LAMBDA (Y)
(IF (EQ X Y)
(DIFF (CAR Y) V)
(CAR Y))))
(CDR E)))))
(CDR E))))))
(bb tex '(diff))
\endlisp
\beginfundef\funlab{diff}
\xx0 diff[e, v] ← \cr
\xx4 \qif \qat e \qthen [\qif e \qeq v \qthen 1 \qelse 0]\cr
\xx4 \qelsif sump e \qthen mksum mapcar[[λx: diff[x, v]], \qd e]\cr
\xx4 \qelsif prodp e \qthen \cr
\xx8 mksum maplist[\cr
\xx{12} [λx: mkprod \cr
\xx{16} maplist[[λy: \qif x \qeq y \qthen diff[\qa y, v]
\qelse \qa y], \qd e]], \cr
\xx{12} \qd e]\cr
\endfundef
The term that describes the rule for differentiating products
corresponds to the rule
$$\partial\div \partial v[\prod_i e_i] =
\sum_i\prod_j[\qif i=j \qthen \partial e_j\div \partial v\qelse e_j].$$
and /maplist\// has to be used rather than /mapcar\// since whether to
differentiate in forming the product is determined by equality of the
indices $i$ and $j$ rather than equality of the terms $e_i$ and
$e_j$.
The internal form for a $\lambda$-expression is
$$|(LAMBDA|\ \langle\hbox{\rm list of variables}\rangle \
\langle\hbox{\rm expression to be evaluated}\rangle|)|.$$
%
Thus $\lambda x. /diff/[x,v]$ is written |(LAMBDA (X) (DIFF X V))|.
The internal form of of /diff\// is given below.
Notice that the function arguments to /maplist\// and /mapcar\// have the form
%
$$|(FUNCTION|\ \langle \hbox{\rm lambda-expression}\rangle|)|.$$
%
This is necessary if the definition is to be compiled as the compiler must
recognize the fact that the following code must be compiled as a function.
\begindefun
(DEFUN DIFF (E V)
(COND ((ATOM E) (IF (EQ E V) 1 0))
((SUMP E)
(MKSUM
(MAPCAR (FUNCTION (LAMBDA (X) (DIFF X V))) (CDR E))))
((PRODP E)
(MKSUM
(MAPLIST (FUNCTION
(LAMBDA (X)
(MKPROD
(MAPLIST (FUNCTION
(LAMBDA (Y)
(IF (EQ X Y)
(DIFF (CAR Y) V)
(CAR Y))))
(CDR E)))))
(CDR E))))))
\enddefun
The above paragraphing (known as ``pretty printing'') makes function
definitions easier to read because items beginning in the same column are
at the same parenthetical level. Also notice that |(QUOTE SEXP)| is
abbreviated to |'SEXP|, however it is important to realize that it is only
an abbreviation; |'SEXP| really reads in as
the list |(QUOTE SEXP)|. This convention
is a feature of all significant \lisp\ implementations.
Two additional useful functions with functions as arguments are the
predicates $andlis$ and $orlis$ defined by the equations
\beginlisp
(DEFUN ANDLIS (PRED U)
(OR (NULL U) (AND (PRED (CAR U)) (ANDLIS PRED (CDR U)))))
(DEFUN ORLIS (PRED U)
(AND (NOT (NULL U)) (OR (PRED (CAR U)) (ORLIS PRED (CDR U)))))
(bb tex '(andlis orlis))
\endlisp
\beginfundef\funlab{andlis}\funlab{orlis}
\xx0 andlis[pred, u] ← \qn u \qor [pred \qa u \qand andlis[pred, \qd
u]]\cr
\noalign{\medskip}
%
\xx0 orlis[pred, u] ← \qnot \qn u \qand [pred \qa u \qor orlis[pred,
\qd u]]\cr
\endfundef
%
\exercise Compute $/diff/[|(* X (+ Y 1) 3)|, |X|]$ using the above
definition of /diff/. The resulting expression requires simplification,
and simplification is a far more difficult problem than differentiation.
\exercise Compute $/orlis/[\qat, |((A B) (C D) E)|].$
\exercise Evaluate the S-expression
$$\vbox{\ialign{&#\hfil\cr
|((LAMBDA (X) (LIST X (LIST (QUOTE QUOTE) X)))| \cr
| (QUOTE (LAMBDA (X)(LIST X (LIST (QUOTE QUOTE) X)))))|\cr
}}$$
and say what its interesting property is. Variants of this expression
have important theoretical properties.
\section{The {\it read eval print\/} loop.}
\sectlab{evaluator}
In this section we give a brief introduction to the {\it toplevel\/} of
\lisp, the so called {\it read eval print\/} loop. Our simplified version of the
{\it toplevel\/} consists of the three programs {\it read},{\it eval\/}
and {\it print\/}
that read evaluate and print S-expressions.
/eval\// plays both a theoretical and a practical role in \lisp.
Historically, the list notation for \lisp\ functions and /eval\// were first
devised in order to show how easy it is to define a universal function in \lisp\ -
the idea was to advocate \lisp\ as an alternative to Turing machines for doing
the elementary theory of computability. This role will be discussed in a later
chapter. S. R. Russell noted that
/eval\// could serve as an interpreter for \lisp\ and promptly programmed it
in machine language with modifications to make it more practical.
An interpreter based on /eval\// has remained a feature of most \lisp\ systems.
Thus when you are talking to \lisp\ the system is in a loop that consists of three
programs
1. /read\// reads what you type and converts it into the corresponding internal
list structure representation,
2. /eval\// then evaluates the internal form in the current environment,
\noindent and
3. /print\// then prints the result back to your terminal (or file etc).
A real \lisp\ system
does many other things too, such a storage management, error handling,
etc. However in our version of the $toplevel$
we shall make several simplifications.
Firstly our {\it toplevel} will not be a loop, we shall only simulate one
interaction
For this reason we define $toplevel$
to have the parameters $exp$ and $env$. $exp$ is the input and $env$
serves as the current environment. Namely
\beginlisp
(DEFUN TOPLEVEL (EXP ENV) (PRINT (EVAL (READ EXP) ENV)))
(bb tex '(toplevel))
\endlisp
\beginfundef
\xx{0} toplevel[exp, env] ← print eval[read exp, env]\cr
\endfundef
$eval$ for \lisp\ expressions is analogous to the
interpreter /numval\// for arithmetic expressions given in \funref{numval}.
The first argument to /eval\// is a \lisp\ expression
in internal notation. The second argument is an association list that
tells /eval\// what value each variable has, and what function definition
is to be associated with each function name. Thus the association list is
a list of pairs where each pair consists either of a variable and the S-expression
corresponding to its value, or a function name and the S-expression
representing the function expression defining the function.
(Here a function expression is either a function name, or a lambda expression.)
The result of applying /eval\// is the value of the term represented by the
S-expression in an
environment where the free variables are assigned the values given by
the association list and where the function names occuring free (i.e. not
bound in a label expression) denote functions defined by the associated
expressions in the association list.
Secondly, what the {\it read\/} program actually does is to get from
the input stream the next string of characters or tokens corresponding to
the external representation of the S-expression. It then constructs the
corresponding internal structure. Rather than deal with the issue of
representing and manipulating character strings, our {\it read\/} and {\it print\/}
programs will assume that the external form is a list of atoms . The special
atoms |RP|, |LP| and |DOT| represent the characters |)|, |(| and ||.
For example the external form of \lisp\ constant |(+ (* A B) C)| is
$$\eqalign{
&|(LP + DOT LP LP * DOT LP A DOT LP |\cr
&\qquad|B DOT NIL RP RP RP DOT LP C DOT NIL RP RP RP)|.\cr}$$
We can inductively define |DOTLIST|, the collection of lists
that represent S-expressions in external form, as follows
1. If $a$ is an atom other than |LP|, |RP| or |DOT| then the list containing $a$ is a
|DOTLIST|.
2. If $L_{car}$ and $L_{cdr}$ are |DOTLIST|s then
$\qlist{|LP|}$ \qapp\ $L_{car}$ \qapp\ $\qlist{|DOT|}$ \qapp\ $L_{cdr}$ \qapp\ $\qlist{|RP|}$
is a |DOTLIST|.
3. Nothing else is a |DOTLIST|.
The problem of reading the more general mixed list-dot notation is deferred
to a later chapter.
Here are the {\it print\/} and {\it read\/} programs
\beginlisp
(DEFUN PRINT (U) (PRINT1 U NIL))
(DEFUN PRINT1 (U L)
(IF (ATOM U)
(CONS U L)
(CONS 'LP (PRINT1 (CAR U) (CONS 'DOT (PRINT1 (CDR U) (CONS 'RP L)))))))
(bb tex '(print print1))
\endlisp
\beginfundef
\xx{0} print u ← print1[u, \qNIL ]\cr
\noalign{\medskip}
\xx{0} print1[u, l] ← \cr
\xx{4} \qif \qat u \qthen u \qcons l \qelse |LP| \qcons print1[\qa
u, |DOT| \qcons print1[\qd u, |RP| \qcons l]]\cr
\endfundef
For example $/print/[|(+ (* A B) C)|]$ is
$$\eqalign{
|(LP + DOT LP LP * DOT LP A DOT LP |\cr
|B DOT NIL RP RP RP DOT LP C DOT NIL RP RP RP)|.\cr}$$
\beginlisp
(DEFUN READ (U) (CAR (READ1 U)))
(DEFUN READ1 (U)
(IF (ATOM U)
'READ-ERROR
(IF (EQ (CAR U) 'LP)
(LET ((W (READ1 (CDR U))))
(IF (OR (ATOM W) (NOT (EQ (CADR W) 'DOT)))
'READ-ERROR
(LET ((V (READ1 (CDDR W))))
(IF (OR (ATOM V)
(NOT (EQ (CADR V) 'RP)))
'READ-ERROR
(CONS (CONS (CAR W) (CAR V))
(CDDR V))))))
U)))
(bb tex '(read read1))
\endlisp
\beginfundef
\xx{0} read u ← \qa read1 u\cr
\noalign{\medskip}
\xx{0} read1 u ← \cr
\xx{4} \qif \qat u \qthen |READ-ERROR|\cr
\xx{4} \qelsif \qa u \qeq |LP| \qthen \cr
\xx{8} \qlet w ← read1 \qd u \cr
\xx{12} \qin \qif \qat w \qor \qnot [\qad w \qeq |DOT|]
\qthen |READ-ERROR|\cr
\xx{15} \qelse \qlet v ← read1 \qdd w \cr
\xx{19} \qin \qif \qat v \qor \qnot [\qad v \qeq
|RP|] \qthen |READ-ERROR|\cr
\xx{22} \qelse [\qa w \qcons \qa v] \qcons \qdd
v\cr
\xx{4} \qelse u\cr
\endfundef
A calculation will reveal that $/read/[/print/[|(+ (* A B) C)|]]$ is
|(+ (* A B) C)|. The reader might care to see if /read\// and /print\//
are in fact inverses of one another, or at least think of the problems involved
in such a task.
A simplified version of the usual \lisp\ /eval\// is the following:
\beginlisp
(DEFUN EVAL1 (E A)
(COND
((CONST? E) E)
((VAR? E) (LOOKUP E A))
((QUOTE? E) (ARG E))
((IF? E) (IF (EVAL (TEST E) A)
(EVAL (THEN E) A)
(EVAL (ELSE E) A)))
((LIST? E) (MAPCAR (FUNCTION (LAMBDA (X) (EVAL X A)))
(BODY E)))
((CAR? E) (CAR (EVAL (ARG E) A)))
((CDR? E) (CDR (EVAL (ARG E) A)))
((CONS? E) (CONS (EVAL (1ST-ARG E) A)
(EVAL (2ND-ARG E) A)))
((ATOM? E) (ATOM (EVAL (ARG E) A)))
((EQ? E) (EQ (EVAL (1ST-ARG E) A) (EVAL (2ND-ARG E) A)))
((ATOMIC-FUNCTION? E) (EVAL (CONS (LOOKUP (FUN E) A) (BODY E)) A))
((LAMBDA? (FUN E)) (EVAL (LAMBDA-BODY E)
(APPEND
(PRUP (LAMBDA-VARS E)
(MAPCAR (FUNCTION (LAMBDA (X)
(EVAL X A)))
(BODY E)))
A))) ) )
(bb tex '(eval1))
\endlisp
\beginfundef
\xx{0} eval[e, a] ← \cr
\xx{4} \qif const? e \qthen e\cr
\xx{4} \qelsif var? e \qthen lookup[e, a]\cr
\xx{4} \qelsif quote? e \qthen arg e\cr
\xx{4} \qelsif if? e \qthen \cr
\xx{8} [\qif eval[test e, a] \qthen eval[then e, a] \qelse eval[
else e, a]]\cr
\xx{4} \qelsif list? e \qthen mapcar[[λx: eval[x, a]], body e]\cr
\xx{4} \qelsif car? e \qthen \qa eval[arg e, a]\cr
\xx{4} \qelsif cdr? e \qthen \qd eval[arg e, a]\cr
\xx{4} \qelsif cons? e \qthen eval[1\!/st-arg/ e, a] \qcons eval
[2\!/nd-arg/ e, a]\cr
\xx{4} \qelsif atom? e \qthen \qat eval[arg e, a]\cr
\xx{4} \qelsif eq? e \qthen eval[1\!/st-arg/ e, a] \qeq eval[2\!/nd-arg/
e, a]\cr
\xx{4} \qelsif /atomic-function/\!? e \qthen eval[lookup[fun e, a] \qcons
body e, a]\cr
\xx{4} \qelsif lambda? fun e \qthen \cr
\xx{8} eval[/lambda-body/ e, \cr
\xx{13} prup[/lambda-vars/ e, mapcar[[λx: eval[x, a]], body e
]] * a]\cr
\endfundef
\beginlisp
(DEFUN PRUP (X Y)
(IF (NULL X)
NIL
(CONS (CONS (CAR X) (CAR Y)) (PRUP (CDR X) (CDR Y)))))
(bb tex '(prup))
(DEFUN TEST (X) (CADR X))
(bb tex '(test))
(DEFUN THEN (X) (CADDR X))
(bb tex '(then))
(DEFUN ELSE (X) (CADDDR X))
(bb tex '(else))
(DEFUN CONST? (X) (OR (NUMBERP X) (EQ X T) (EQ X NIL)))
(bb tex '(const?))
(DEFUN VAR? (X) (ATOM X))
(bb tex '(var?))
(DEFUN QUOTE? (X) (EQ (CAR X) 'QUOTE))
(bb tex '(quote?))
(DEFUN IF? (X) (EQ (CAR X) 'IF))
(bb tex '(if?))
(DEFUN LIST? (X) (EQ (CAR X) 'LIST))
(bb tex '(list?))
(DEFUN CAR? (X) (EQ (CAR X) 'CAR))
(bb tex '(car?))
(DEFUN CDR? (X) (EQ (CAR X) 'CDR))
(bb tex '(cdr?))
(DEFUN CONS? (X) (EQ (CAR X) 'CONS))
(bb tex '(cons?))
(DEFUN ATOM? (X) (EQ (CAR X) 'ATOM))
(bb tex '(atom?))
(DEFUN EQ? (X) (EQ (CAR X) 'EQ))
(bb tex '(eq?))
(DEFUN LAMBDA? (X) (EQ (CAR X) 'LAMBDA))
(bb tex '(lambda?))
(DEFUN ARG (X) (CADR X))
(bb tex '(arg))
(DEFUN BODY (X) (CDR X))
(bb tex '(body))
(DEFUN FUN (X) (CAR X))
(bb tex '(fun))
(DEFUN ATOMIC-FUNCTION? (X) (ATOM (CAR X)))
(bb tex '(atomic-function?))
(DEFUN 1ST-ARG (X) (CADR X))
(bb tex '(1st-arg))
(DEFUN 2ND-ARG (X) (CADDR X))
(bb tex '(2nd-arg))
(DEFUN LAMBDA-BODY (X) (CADDAR X))
(bb tex '(lambda-body))
(DEFUN LAMBDA-VARS (X) (CADAR X))
(bb tex '(lambda-vars))
\endlisp
\beginfig{h}{Auxiliary functions used by $eval$}
\beginfundef
\hskip0\unit prup[x, y] ← \qif \qn x \qthen \qNIL
\qelse [\qa x \qcons \qa y] \qcons prup[\qd x, \qd y]\cr
%
\hskip0\unit test x ← \qad x\cr
%
\hskip0\unit then x ← \qadd x\cr
%
\hskip0\unit else x ← \qaddd x\cr
%
\hskip0\unit const? x ← numberp x \qor x \qeq
\qT \qor x \qeq \qNIL \cr
%
\hskip0\unit var? x ← \qat x\cr
%
\hskip0\unit quote? x ← \qa x \qeq |QUOTE|\cr
%
\hskip0\unit if? x ← \qa x \qeq |IF|\cr
%
\hskip0\unit list? x ← \qa x \qeq |LIST|\cr
%
\hskip0\unit car? x ← \qa x \qeq |CAR|\cr
%
\hskip0\unit cdr? x ← \qa x \qeq |CDR|\cr
%
\hskip0\unit cons? x ← \qa x \qeq |CONS|\cr
%
\hskip0\unit atom? x ← \qa x \qeq |ATOM|\cr
%
\hskip0\unit eq? x ← \qa x \qeq |EQ|\cr
%
\hskip0\unit lambda? x ← \qa x \qeq |LAMBDA|\cr
%
\hskip0\unit arg x ← \qad x\cr
%
\hskip0\unit body x ← \qd x\cr
%
\hskip0\unit fun x ← \qa x\cr
%
\hskip0\unit /atomic-function/\!? x ← \qat \qa x\cr
%
\hskip0\unit 1\!/st-arg/ x ← \qad x\cr
%
\hskip0\unit 2\!/nd-arg/ x ← \qadd x\cr
%
\hskip0\unit /lambda-body/ x ← \qadda x\cr
%
\hskip0\unit /lambda-vars/ x ← \qada x\cr
\endfundef
\endfig
This simple /eval\// expects that an expression is either a
constant ({\it number}, \qT, \qNIL, or a |QUOTE|d S-expression),
a variable whose value can be found on the association list,
a conditional expression, a list making
expression, or an application of a function or lambda expression
to a list of arguments. Thus /eval\// checks to see
which of the above classes the expression to be evaluated falls into
and proceeds accordingly. If the expression, $e$, is atomic then it is either
a non |QUOTE|d constant or a variable. If the former then /eval\// just returns
the expression, if the latter it looks up the value on the association list, $a$.
To illustrate the way {\it eval\/} works,
suppose we want to apply the function /alt\//
to the list |(A B C D E)|. That is, we wish to evaluate $/alt/[|(A B C D E)|]$.
This can be obtained by computing
$$\vbox{\ialign{#\hfil&#\hfil\cr
/eval/[&|(ALT (QUOTE (A B C D E))),|\cr
&|((ALT LAMBDA (X)|\cr
&| (COND ((OR (NULL X) (NULL (CDR X))) X)|\cr
&| (T (CONS (CAR X) (ALT (CDDR X)))))))|].\cr
}}$$
Some discussion of how the /eval\// goes about its task might be helpful.
If $e$ is non-atomic but $/fun\//[e]$ is atomic (i.e $\qa e$ is atomic)
then $e$ is either
a |QUOTE|d constant, a conditional, a list maker, or an application of a
function to a list of arguments. In the constant case the expression
being quoted $/arg\//[e]$ (i.e $\qad e$) is returned. If $e$ is a conditional
then $/test\//[e]$
is evaluated if it returns |NIL| then $/else\//[e]$ is evaluated and
the value returned,if $/test\//[e]$
returns a value other than |NIL| then $/then\//[e]$ is evaluated and the
value returned.
In the list case the list of expressions to be evaluated
by mapping {\it eval\/} down $/body\//[e]$ using /mapcar/.
In the function application case there are two
possibilities. If the function to be applied
is one of the elementary functions, the indicated operation is performed
on the result of evaluating the arguments. Otherwise the function must
be defined in $a$, so /eval\// looks up the definition, replaces the function
name by the function definition in the expression and restarts the evaluation.
If neither $e$ nor $/fun\//[e]$ are atomic then it must be a lambda
application. In the lambda case the argument list is
evaluated, the values are then paired with the list of variables to be
bound by the lambda ($/lambda-vars\//[e]$) using /prup\//
and put on the front of $a$.
The body of the lambda ($/lambda-body\//[e]$) is then evaluated using this new
association list.
If $e$ is not an expression of the sort expected by /eval/, then
the result is not defined. It would not be difficult to add additional
clauses to /eval\// so that it would return reasonable error messages rather
than just being undefined (or dying in some strange way as would be
likely in an actual computer). It would be necessary to be make the
error messages distinguishable from legitimate values of the expression
so that errors at inner levels of evaluation could be passed up the chain.
This could be done by returning legitimate values as pairs whose first
element is one atom and error messages as pairs prefixed by another.
Terms containing /eval\// would have to distinguish the cases.
Notice that
\qif and /list\// considered as pseudo-functions behave differently
than ordinary functions. Firstly, /list\// can take
an arbitrary number of arguments while functions defined by a lambda
expression have a fixed number of arguments determined by the variable list
occuring in the lambda expression. Secondly the usual manner of evaluation
an application term is \lisp\ is to evaluate all of the arguments then
apply the function. This will not work for \qif as the main reason for
a conditional is to be able to select a term to evaluate depending on
some set of conditions and not to evaluate other terms under those conditions.
The above version of /eval\// does not handle the propositional
constructs \qand, \qor, \qnot\ and |COND|. The effect of these constructs
can be obtained by appropriate use of \qif, but simply
defining functions for \qand\ and \qor\ will not work as the evaluation
of a function application requires that all of the arguments of
of the function be evaluated before it is applied while the specification
of \qand\ and \qor\ require that only as many of the arguments be evaluated
as are required to determine the answer.
Another problem is that in most implementations
they are allowed to take an arbitrary number of arguments. Thus
we need to build them into /eval\// for things to work properly.
We will see later that \lisp\ systems provide alternate solutions to
this problem by providing a variety of modes of function application.
(These are known as |EXPR| and |LEXPR|s.) Macros are also
used for this purpose and will be explained later. Arithmetic is
also missing from our /eval/. Adding these constructs is essentially
like combining /eval\// with the earlier evaluator /numval\// and adding
any additional primitive operations that are desired.
We note that /eval\// can evaluate itself if it is given an
association list, /eval-alist/, containing the definition of /eval\//
and the auxiliary functions involved
written as s-expressions. Thus
$$/eval\/\//[|(EVAL '(CAR '(A.B)) NIL)|,/eval-alist/= |A|.$$
\exercise What is the value of
$$\vbox{\ialign{\hfil$#$&$#$\hfil\cr
/eval\/\//[&|(LEFT (QUOTE (A . B)))|,\cr
&|((LEFT LAMBDA (X) (COND ((ATOM X) X) (T (LEFT (CAR X))))))|]?\cr
}}$$
\exercise Rewrite the definition of $read1$ without using the $\lambda$ construct.
Which program is more efficient?
\exercise Translate the definition of /eval\// given above into internal notation.
\exercise Go to your nearest \lisp\ system, type in your answer to the second exercise
and use it to check your answer to the first exercise.
\exercise Extend the function {\it eval\/} so that it handles the logical operations
\qand, \qor, \qnot\ and |COND|, you may need to read the next chapter before doing
this.